无糖乌龙

没有明天的烂人

网络流模板

发布于 2020-07-25 | 14分钟 | 2102字数

dinic(无当前弧优化)

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4+7,M = 2e5+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],now[M];
int incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;now[s] = ver[s];
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				now[v] = ver[v];
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	now[u] = i;
	return flow - rest;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	while(m--)
	{
		int u,v,c;scanf("%d%d%d",&u,&v,&c);
		add(u,v,c);
	}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	printf("%d",maxflow);
    return 0;
}

EK

const int N = 1005,M = 2e5+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,st[N],pre[N];
ll incf[N],maxflow;
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
void update()
{
	int x = t;
	while(x != s)
	{
		int i = pre[x];
		cap[i] -= incf[t];
		cap[i ^ 1] += incf[t];
		x = edge[i ^ 1];
	}
	maxflow += incf[t];
}
bool bfs()
{
	memset(st,0,sizeof st);
	queue<int> q;q.push(s);st[s] = 1;
	incf[s] = INF;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int j = cap[i];
			if(j)
			{
				int v = edge[i];
				if(st[v])	continue;
				incf[v] = min(incf[u],1ll*j);
				pre[v] = i;
				q.push(v);
				st[v] = 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	while(m--)
	{
		int u,v,c;scanf("%d%d%d",&u,&v,&c);
		add(u,v,c);
	}
	while(bfs())	update();
	printf("%lld",maxflow);
    return 0;
}

dinic(当前弧优化)

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 20000,M = 100000 * 2,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N];
ll incf[N],maxflow;
int q[M],hh,tt;
void add(int u,int v,int w)
{
	edge[idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx++; 
	
	edge[idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx++;
}
bool bfs()
{
	memset(d,0,sizeof d);
	hh = 0,tt = -1;
	q[++tt] = s;d[s] = 1;now[s] = ver[s];
	while(hh <= tt)
	{
		int u = q[hh++];
		for(int i = ver[u];~i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q[++tt] = v;
				now[v] = ver[v];
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int limit)
{
	if(u == t)	return limit;
	int flow = 0,k;
	for(int i = now[u];~i && flow < limit;i = succ[i])
	{
		now[u] = i;
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(limit - flow,cap[i]));
			if(!k)	d[v] = -1;
			cap[i] -= k;
			cap[i ^ 1] += k;
			flow += k;
		}
	}
	return flow;
}
int main()
{
	memset(ver,-1,sizeof ver);
	scanf("%d%d%d%d",&n,&m,&s,&t);
	while(m--)
	{
		int u,v,c;scanf("%d%d%d",&u,&v,&c);
		add(u,v,c);
	}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	printf("%lld",maxflow);
    return 0;
}

#无源汇上下界可行流

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 405,M = 10200 * 4,INF = 1 << 29;
int edge[M],succ[M],caplow[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],sub[N];
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int wlow,int wup)
{
	edge[idx] = v;
	cap[idx] = wup - wlow;
	caplow[idx] = wlow;
	succ[idx] = ver[u];
	ver[u] = idx++; 
	
	edge[idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx++;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	memset(ver,-1,sizeof ver);
	scanf("%d%d",&n,&m);
	s = 0;t = n + 1;
	for(int i = 0;i < m;++i)
	{
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		sub[a] -= c;sub[b] += c;
		add(a,b,c,d);
	}
	ll allflow = 0;
	for(int i = 1;i <= n;++i)
	{
		if(sub[i] > 0)	add(s,i,0,sub[i]),allflow += sub[i];
		else if(sub[i] < 0)	add(i,t,0,-sub[i]);
	}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
    if(allflow == maxflow)
    {
    	puts("YES");
    	for(int i = 0;i < m * 2;i += 2)
    	{
    		int u = edge[i],v = edge[i ^ 1];
    		if(u == s || u == t || v == u || v == t)	continue;
    		printf("%d\n",cap[i ^ 1] + caplow[i]);
    	}
    		
    }
    else puts("NO");
    return 0;
}

有源汇上下界最大流

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 20000,M = 100000 * 2,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N],sub[N];
ll incf[N],maxflow;
int q[M],hh,tt;
void add(int u,int v,int w)
{
	edge[idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx++; 
	
	edge[idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx++;
}
bool bfs()
{
	memset(d,0,sizeof d);
	hh = 0,tt = -1;
	q[++tt] = s;d[s] = 1;now[s] = ver[s];
	while(hh <= tt)
	{
		int u = q[hh++];
		for(int i = ver[u];~i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q[++tt] = v;
				now[v] = ver[v];
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int limit)
{
	if(u == t)	return limit;
	int flow = 0,k;
	for(int i = now[u];~i && flow < limit;i = succ[i])
	{
		now[u] = i;
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(limit - flow,cap[i]));
			if(!k)	d[v] = -1;
			cap[i] -= k;
			cap[i ^ 1] += k;
			flow += k;
		}
	}
	return flow;
}
int main()
{
	memset(ver,-1,sizeof ver);
	int S,T;scanf("%d%d%d%d",&n,&m,&S,&T);
	s = 0,t = n + 1;
	while(m--)
	{
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		add(a,b,d - c);
		sub[a] -= c;sub[b] += c;
	}
	ll allflow = 0;
	for(int i = 1;i <= n;++i)
		if(sub[i] > 0)	add(s,i,sub[i]),allflow += sub[i];
		else if(sub[i] < 0)	add(i,t,-sub[i]);
	add(T,S,INF);
	int flow;
	while(bfs())
		while(flow = dinic(s,INF))
			maxflow += flow;
	if(maxflow < allflow)	puts("No Solution");
	else
	{
		int pres = cap[idx - 1];
		cap[idx - 1] = cap[idx - 2] = 0;
		flow = 0;maxflow = 0;
		s = S;t = T;
		while(bfs())
			while(flow = dinic(s,INF))
				maxflow += flow;
		printf("%lld",pres + maxflow);
	}
    return 0;
}

有源汇上下界最小流

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 50070,M = 125003 * 4,INF = 2147483647;
int edge[M],succ[M],cap[M],ver[N],idx;
int n,m,s,t,d[N],pre[N],now[N],sub[N];
ll incf[N],maxflow;
int q[M],hh,tt;
void add(int u,int v,int w)
{
	edge[idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx++; 
	
	edge[idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx++;
}
bool bfs()
{
	memset(d,0,sizeof d);
	hh = 0,tt = -1;
	q[++tt] = s;d[s] = 1;now[s] = ver[s];
	while(hh <= tt)
	{
		int u = q[hh++];
		for(int i = ver[u];~i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q[++tt] = v;
				now[v] = ver[v];
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int limit)
{
	if(u == t)	return limit;
	int flow = 0,k;
	for(int i = now[u];~i && flow < limit;i = succ[i])
	{
		now[u] = i;
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(limit - flow,cap[i]));
			if(!k)	d[v] = -1;
			cap[i] -= k;
			cap[i ^ 1] += k;
			flow += k;
		}
	}
	return flow;
}
int main()
{
	memset(ver,-1,sizeof ver);
	int S,T;scanf("%d%d%d%d",&n,&m,&S,&T);
	s = 0,t = n + 1;
	while(m--)
	{
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		add(a,b,d - c);
		sub[a] -= c;sub[b] += c;
	}
	ll allflow = 0;
	for(int i = 1;i <= n;++i)
		if(sub[i] > 0)	add(s,i,sub[i]),allflow += sub[i];
		else if(sub[i] < 0)	add(i,t,-sub[i]);
	add(T,S,INF);
	int flow;
	while(bfs())
		while(flow = dinic(s,INF))
			maxflow += flow;
	// cout << maxflow << endl;
	if(maxflow < allflow)	puts("No Solution");
	else
	{
		int pres = cap[idx - 1];
		cap[idx - 1] = cap[idx - 2] = 0;
		flow = 0;maxflow = 0;
		s = T;t = S;
		while(bfs())
			while(flow = dinic(s,INF))
				maxflow += flow;
		printf("%lld",pres - maxflow);
	}
    return 0;
}
Powered by Gridea | © 2019-2020 Theme By HsxyHao
没有明天的人
0%